"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        
        # 找root的最近右侧可用孩子
        def next(root:'Node'):
            if root is None or root.next is None:
                return None
            if root.next.left is not None:
                return root.next.left
            if root.next.right is  not None:
                return root.next.right
            return next(root.next)
            
        # 完成题目要求
        def f(root:'Node'):
            if root is None:
                return
            if root.left is not None:
                root.left.next = root.right if root.right is not None else next(root)
            if root.right is not None and root.next is not None:
                root.right.next = next(root)
            f(root.right) # 先右
            f(root.left) # 再左

        f(root)
        return root